9.7 Show that if t is a complete binary tree, then height(t ) = floor(log2(n(t ))) Hint: Let t be a complete binary tree of height k ≥ 0, and let t1 be a full binary tree of height k − 1. Then n(t1) + 1 ≤ n(t ). Use Part 4 of the Binary Tree Theorem to show that floor(log2 (n(t1) + 1)) = k, and use Part 1 of the Binary Tree Theorem to show that floor(log2(n(t ))) < k + 1. | |
| View Solution | |
| << Back | Next >> |